package leetcode.editor.cn.dsa08_hashtable;
//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

public class LongestSubstringWithoutRepeatingCharacters3_2 {
    public static void main(String[] args) {
        Solution solution =
                new LongestSubstringWithoutRepeatingCharacters3_2().new Solution();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); //3
        System.out.println(solution.lengthOfLongestSubstring("dvdf")); //3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb")); //1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew")); //3
        System.out.println(solution.lengthOfLongestSubstring("")); //0
        System.out.println(solution.lengthOfLongestSubstring("abcdefg")); //7
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解法二：优化解法，使用语言特性
         * 1.定义变量 maxLength 表示最大长度
         * 2.使用双指针截取不含重复字符的子串
         * 3.计算子串长度，保留较大值到 maxLength
         *
         * @param s
         * @return
         */
        public int lengthOfLongestSubstring(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) return 0;
            // 1.定义变量 maxLength 表示最长子串的长度。默认值1
            int maxLength = 1;
            int end = 1;
            // 2.使用双指针截取不含重复字符的子串
            for (int start = 0; start < len; start++) { // 遍历子串的起始字符
                // 优化点：每次循环后动态调整end值，而不是固定start+1
                // 每次截取完一个子串，end所在位置前面必定是不重复的字符了
                // 当然也有可能位置没动，所以还需要比较一下
                end = end > start + 1 ? end : start + 1;
                for (; end < len; end++) { // 遍历子串的终止字符
                    // 当前字符在前面的子串中已出现，该子串到此结束
                    // 优化点：从start位置开始判断，不用每次都截取字符串了
                    // 只要索引范围在[start, end)，说明已重复
                    int idx = s.indexOf(s.charAt(end), start);
                    if (idx >= start && idx < end) {
                        break;
                    }
                }
                // 3.计算子串长度，保留较大值到 maxLength
                int subLen = end - start;
                if (subLen > maxLength) {
                    maxLength = subLen;
                }
                // 如果遍历到结尾了，说明后面的字符都是不重复的，无需继续遍历了
                if (end == len) break;
            }
            return maxLength;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}

